import java.util.*;

public class Solution {
    /**
     * 2025.2.3 (1)
     * 判定是否互为字符重排
     * @param s1
     * @param s2
     * @return
     */
    public boolean CheckPermutation(String s1, String s2) {
        // 判断长度是否相同
        if (s1.length() != s2.length()) {
            return false;
        }
        // 存储 s1 中字母种类和个数
        int[] hash = new int[26];
        for(int i = 0; i < s1.length(); i++) {
            hash[s1.charAt(i) - 'a']++;
        }
        // 判断 s2 中字母种类和个数是否与 s1 中相同
        int[] hash2 = new int[26];
        for(int i = 0; i < s2.length(); i++) {
            int index = s2.charAt(i) - 'a';
            hash2[index]++;
            if (hash2[index] > hash[index]) {
                return false;
            }
        }
        for(int i = 0; i < hash.length; i++) {
            if (hash[i] != hash2[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 2025.2.3 (2)
     * 在排序数组中查找元素的第一个和最后一个位置
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        if (nums.length <= 0) {
            return new int[] {-1, -1};
        }
        int[] res = new int[2];
        // 查找第一个位置
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] != target) {
            return new int[] {-1, -1};
        }
        res[0] = left;
        // 查找最后一个位置
        left = 0;
        right = nums.length - 1;
        while(left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        res[1] = right;
        return res;
    }

    /**
     * 2025.2.4 (1)
     * 验证回文串II
     * 动态规划——超出内存限制
     * @param s
     * @return
     */
    public boolean validPalindrome(String s) {
        // 动态规划
        int len = s.length();
        s = " " + s;
        // 创建 dp 表
        int[][] dp = new int[len + 1][len + 1];
        // 初始化
        // 填表
        for(int i = len; i >= 1; i--) {
            for(int j = i; j <= len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i + 1 == j) {

                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        // 返回
        return dp[1][len] <= 1;
    }

    /**
     *
     * 2025.2.4 (1)
     * 验证回文串II
     * 贪心
     * @param s
     * @return
     */
    public boolean validPalindrome2(String s) {
        int left = 0, right = s.length() - 1;
        while(left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return judegPalindrome(s, left, right - 1) || judegPalindrome(s, left + 1, right);
            }
        }
        return true;
    }
    public boolean judegPalindrome(String s, int left, int right) {
        if (s.length() <= 1) {
            return true;
        }
        while(left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * 2025.2.4 (2)
     * x 的平方根
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        // 二分查找
        long left = 1, right = x;
        while(left < right) {
            long mid = (left + right + 1) / 2;
            if (mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int) left;
    }

    /**
     * 2025.2.5 (1)
     * 宝石与石头
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        // 统计宝石的种类
        Set<Character> hash = new HashSet<>();
        for(int i = 0; i < jewels.length(); i++) {
            hash.add(jewels.charAt(i));
        }
        // 寻找宝石
        int count = 0;
        for(int i = 0; i < stones.length(); i++) {
            if (hash.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    /**
     * 2025.2.5 (2)
     * 快乐数
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        int slow = n;
        int fast = sumOfSquares(n);
        while(slow != fast) {
            slow = sumOfSquares(slow);
            fast = sumOfSquares(sumOfSquares(fast));
        }
        return slow == 1;
    }

    public int sumOfSquares(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }


    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;

    /**
     * 2025.2.6 (1)
     * 全排列II
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        Arrays.sort(nums);
        check = new boolean[nums.length];
        dfs(nums, 0);
        return ret;
    }
    public void dfs(int[] nums, int index){
        //递归出口
        if(index == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(check[i] == false
                    && (i == 0
                        || nums[i] != nums[i - 1]
                        || check[i - 1] != false)){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums, index + 1);
                //回溯
                path.remove(path.size() - 1);
                check[i] = false;
            }
        }
    }
    /**
     * 2025.2.6 (2)
     * 盛最多水的容器
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, area = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            if (h * (right - left) > area) {
                area = h * (right - left);
            }
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return area;
    }

    /**
     * 2025.2.7 (1)
     * 最大子数组和
     * 动态规划 二维dp—— 超出内存限制
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        // 创建 dp 表
        int[][] dp = new int[len + 1][len + 1];
        // 初始化
        int max = Integer.MIN_VALUE;
        // 填表
        for(int i = 1; i <= len; i++) {
            for(int j = i; j <= len; j++) {
                dp[i][j] = dp[i][j - 1] + nums[j - 1];
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        return max;
    }

    /**
     * 2025.2.7 (1)
     * 最大子数组和
     * 动态规划 一维 dp
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int len = nums.length;
        // 创建 dp 表
        int[] dp = new int[len + 1];
        // 初始化
        int max = Integer.MIN_VALUE;
        // 填表
        for(int i = 1; i <= len; i++) {
            dp[i] = Math.max(nums[i - 1], dp[i - 1] +nums[i - 1]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * 2025.2.7 (2)
     * 除自身以外数组的乘积
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        // 创建 dp 表
        int[] pre = new int[len];
        int[] suf = new int[len];
        // 初始化
        for(int i = 0; i < len; i++) {
            pre[i] = suf[i] = 1;
        }
        // 填表
        for(int i = 1; i < len; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        for(int i = len - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        int[] ret = new int[len];
        for(int i = 0; i < len; i++) {
            ret[i] = pre[i] * suf[i];
        }
        return ret;
    }


    /**
     * 2025.2.10 (1)
     * 逆波兰表达式求值
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            if (isOperator(tokens[i])) {
                int num1 = stack.pop();
                int num2 = stack.pop();
                if (tokens[i].equals("+")) {
                    stack.push(num1 + num2);
                } else if (tokens[i].equals("-")) {
                    stack.push(num2 - num1);
                } else if (tokens[i].equals("*")) {
                    stack.push(num1 * num2);
                } else if (tokens[i].equals("/")) {
                    stack.push(num2 / num1);
                }
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }
    public boolean isOperator(String str) {
        if (str.equals("+")
                || str.equals("-")
                || str.equals("*")
                || str.equals("/")) {
            return true;
        }
        return false;
    }


    /**
     * 2025.2.10 (2)
     * 判定字符是否唯一
     * @param astr
     * @return
     */
    public boolean isUnique(String astr) {

        int n = 0;
        for(int i = 0; i < astr.length(); i++) {
            int index = astr.charAt(i) - 'a';
            if ((n >> index & 1) == 1) {
                return false;
            } else {
                n = (1 << index) | n;
            }
        }
        return true;
    }

    /**
     * 2025.2.11 (1)
     * 漂亮数组
     */
    Map<Integer, int[]> hash;
    public int[] beautifulArray(int n) {
        hash = new HashMap<>();
        hash.put(1, new int[]{1});
        return fun(n);
    }

    public int[] fun(int n) {
        if (!hash.containsKey(n)) {
            int index = 0;
            int[] res = new int[n];
            for(int i: fun((n + 1) / 2)) {
                res[index++] = 2 * i - 1;
            }
            for(int i: fun(n / 2)) {
                res[index++] = 2 * i;
            }
            hash.put(n, res);
        }
        return hash.get(n);
    }

    /**
     * 2025.2.11 (2)
     * 丢失的数字
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int n = 0;
        int len = nums.length;
        for(int i = 1; i <= len; i++) {
            n ^= i;
        }
        for(int i = 0; i < len; i++) {
            n ^= nums[i];
        }
        return n;
    }

    /**
     * 2025.2.12 (2)
     * 打家劫舍
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int len = nums.length;
        // 创建 dp 表
        int[] f = new int[len]; // 选 i
        int[] g = new int[len]; // 不选 i
        // 初始化
        f[0] = nums[0];
        int max = f[0];
        // 填表
        for(int i = 1; i < len; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1], g[i-1]);
            max = Math.max(max, Math.max(f[i], g[i]));
        }
        // 返回
        return max;
    }

    /**
     * 2025.2.12 (1)
     * 最大数
     * @param nums
     * @return
     */
    public String largestNumber(int[] nums) {
        // 将数字转化为字符串
        int len = nums.length;
        String[] strs = new String[len];
        for(int i = 0; i < len; i++) {
            strs[i] = "" + nums[i];
        }
        // 对字符串数组进行排序
        Arrays.sort(strs, (a, b) -> {
            return (b + a).compareTo(a + b);
        });
        String ret = "";
        for (int i = 0; i < len; i++) {
            ret += strs[i];
        }
        // 处理特殊请求
        if (ret.charAt(0) == '0') {
            ret = "0";
        }
        return ret;
    }

    /**
     * 2025.2.13 (1)
     * 最短无序连续子数组
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int min = nums[len - 1];
        int max = nums[0];
        int begin = 0, end = -1;
        for(int i = 0; i < len; i++) {
            // 从左到右维持最大值，寻找右边界值
            if (nums[i] < max) {
                end = i;
            } else {
                max = nums[i];
            }
            // 从右到左维持最小值，寻找左边界
            if (nums[len - i - 1] > min) {
                begin = len - i - 1;
            } else {
                min = nums[len - i - 1];
            }
        }
        return end - begin + 1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3,1};
        solution.rob(nums);
    }
}
